//
// Created by francklinson on 2021/10/26 AT 9:47.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>


//using namespace std;
class Solution {
public:
    std::vector<int> nextGreaterElement(std::vector<int> &nums1, std::vector<int> &nums2) {
        std::stack<int> s;
        std::unordered_map<int, int> um;
        // 先对nums2进行处理，得到每个数字右侧的第一个更大的值，用单调栈实现
        for (int i = nums2.size() - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!s.empty() and num > s.top())
                s.pop();
            um[num] = s.empty() ? -1 : s.top();
            s.push(num);
        }
        std::vector<int> ans(nums1.size());
        for (int i = 0; i < nums1.size(); ++i) {
            ans[i] = um[nums1[i]];
        }
        return ans;
    }
};

int main() {
    std::vector<int> nums1{4, 1, 2};
    std::vector<int> nums2{1, 3, 4, 2};
    Solution solution;
    std::vector<int> ans = solution.nextGreaterElement(nums1, nums2);
    for (const int &x: ans) std::cout << x << std::endl;
    return 0;
}

